package Class009;

import BasicDataStructures.ListNode;
import Utils.ListUtils;

//划分链表
//大于等于n的放右边，小于n的放左边
//不能改变相对次序
public class SplitList {
    public static void main(String[] args) {
        int[] val = {6, 5, 3, 4, 2, 1, 1, 7};
        ListNode head = ListUtils.generateList(val);
        ListUtils.printList(head);
        ListNode newHead = splitList(head, 0);
        ListUtils.printList(newHead);
        ListNode newHead_1 = splitList(head, 8);
        ListUtils.printList(newHead_1);
        ListNode newHead_2 = splitList(head, 3);
        ListUtils.printList(newHead_2);
    }

    public static ListNode splitList(ListNode head, int val) {
        if(head == null) return null;
        ListNode smallCur = null;
        ListNode smallHead = null;

        ListNode biggerCur = null;
        ListNode biggerHead = null;
        while(head != null) {
            if(head.val < val) {
                if(smallHead == null) {
                    smallHead = head;
                }else {
                    smallCur.next = head;
                }
                smallCur = head;
            }else {
                if(biggerHead == null) {
                    biggerHead = head;
                }else {
                    biggerCur.next = head;
                }
                biggerCur = head;
            }
            head = head.next;
        }
        if(smallCur != null) smallCur.next = biggerHead;
        return smallHead == null ? biggerHead : smallHead;
    }


}
